package leetcode_zh

/**
 * @Description: 23. 合并K个升序链表
 * @Keyword: 分而治之
 * @Author: kami
 * @Date: 2022/5/23 10:31
 **/
func mergeKLists(lists []*ListNode) *ListNode {
	if len(lists) == 1 {
		return lists[0]
	} else if len(lists) == 2 {
		return mergeTwoSortLists(lists[0], lists[1])
	} else if len(lists) == 0 {
		return nil
	}
	var count = len(lists)
	var idx = 0
	for count > 1 {
		var curCount = count
		for i := 0; i < count; i += 2 {
			if i == count-1 {
				lists[idx] = lists[i]
			} else {
				lists[idx] = mergeTwoSortLists(lists[i], lists[i+1])
				curCount--
			}
			idx++
		}
		idx = 0
		count = curCount
	}

	return lists[0]
}

func mergeTwoSortLists(head1, head2 *ListNode) *ListNode {
	if head1 == nil {
		return head2
	} else if head2 == nil {
		return head1
	}
	var resHead *ListNode
	if head1.Val > head2.Val {
		resHead = head2
		head2 = head2.Next
	} else {
		resHead = head1
		head1 = head1.Next
	}
	var preHead = resHead
	for head1 != nil || head2 != nil {
		if head1 != nil && head2 != nil {
			if head1.Val > head2.Val {
				preHead.Next = head2
				head2 = head2.Next
			} else {
				preHead.Next = head1
				head1 = head1.Next
			}
			preHead = preHead.Next
		} else if head1 != nil {
			preHead.Next = head1
			break
		} else {
			preHead.Next = head2
			break
		}
	}

	return resHead
}

/**
 * @Description: 460. LFU 缓存 困难
 * @Keyword: 最近最少访问，按照频率来的
 * @Author: kami
 * @Date: 2022/6/22 13:41
 **/
type LFUCache struct {
	// 最大容量
	capacity int
	// 数据 数据：访问次数
	dataMap map[int]*Data
	// 访问频率，访问频率：该频率下的数据链表的头结点
	frequentMap map[int]*Data
	// 最小访问频率
	minFreq int
}

type Data struct {
	// 值
	val int
	// 频率
	fre  int
	pre  *Data
	next *Data
}

func ConstructorLfu(capacity int) LFUCache {
	return LFUCache{
		capacity:    capacity,
		dataMap:     make(map[int]*Data),
		frequentMap: make(map[int]*Data),
	}
}

func (this *LFUCache) Get(key int) int {
	if V, ok := this.dataMap[key]; ok {
		this.increaseFreq(V)
		return V.val
	}
	return -1
}

func (this *LFUCache) Put(key int, value int) {
	if V, ok := this.dataMap[key]; ok {
		if V.val != value {
			V.val = value
		}
		this.increaseFreq(V)
		return
	}
	// 容量满，去除最小频率头结点
	if len(this.dataMap) == this.capacity {
		if V, ok := this.frequentMap[this.minFreq]; ok {
			// 如果只有一个节点
			if V.next == nil {
				this.frequentMap[this.minFreq] = nil
				delete(this.frequentMap, this.minFreq)
			} else {
				this.frequentMap[this.minFreq] = V.next
				V.next.pre = nil
				V.next = nil
			}
			delete(this.dataMap, V.val)
		}
	}
	newData := &Data{
		val: value,
		fre: 1,
	}
	this.minFreq = 1
	if V, ok := this.frequentMap[this.minFreq]; ok {
		for V.next != nil {
			V = V.next
		}
		V.next = newData
		newData.pre = V
	} else {
		this.frequentMap[this.minFreq] = newData
	}
	this.dataMap[newData.val] = newData
}

func (this *LFUCache) increaseFreq(data *Data) {
	// 原频率链表中去除
	this.removeFrequentNode(data)
	// 访问频率+1
	if data.fre == this.minFreq && this.frequentMap[this.minFreq] == nil {
		this.minFreq++
	}
	data.fre++
	// 新频率链表中增加
	this.addToNewFrequentList(data)
}

func (this *LFUCache) addToNewFrequentList(data *Data) {
	// 添加在尾部
	if head, ok := this.frequentMap[data.fre]; ok {
		for head.next != nil {
			head = head.next
		}
		head.next = data
		data.pre = head
		return
	}
	this.frequentMap[data.fre] = data
}

func (this *LFUCache) removeFrequentNode(data *Data) {
	if data.pre == nil && data.next == nil {
		// 链表只有1个节点，则去除此频率链表
		delete(this.frequentMap, data.fre)
	} else if data.pre == nil {
		// 头结点后移
		this.frequentMap[data.fre] = data.next
		data.next = nil
	} else if data.next == nil {
		// 尾节点
		data.pre.next = nil
		data.pre = nil
	} else {
		data.pre.next = data.next
		data.next.pre = data.pre
		data.pre = nil
		data.next = nil
	}
}

/**
 * Your LFUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */
